Technical Field
The present description relates to techniques for implementing an encryption method using a look-up table.
Description of the Related Art
Look-up tables (LUTs), also referred to as association tables, are data structures that enable association to any admissible combination of input data of a corresponding (not necessarily unique) configuration of output data. Normally, the use of a look-up table makes it possible to speed up operations, in so far as access to the datum in the table is faster than calculation of the datum itself.
Look-up tables are hence frequently used in encryption algorithms, whether hardware or software, to carry out complex calculations. For example, a look-up table, the so-called “Substitution Box” or “S-Box,” is used in the known AES (Advanced Encryption Standard) encryption algorithm for implementing operations such as, for example, the SubBytes operation.
In order to discover the key, in particular of symmetric-key block-encryption algorithms, such as the AES algorithm, but even algorithms with non-symmetric public key, it is known to use the so-called side-channel attacks, e.g., attacks that exploit the information that can be derived, through a so-called leakage process, e.g., a process of leakage of information, from physical implementation of the encryption procedure, for example by measuring the energy absorption of the circuit.
Several of the countermeasures against the above side-channel attacks exploit the presence of look-up tables in the circuits that implement the algorithms, performing operations of initialization of the values contained in these tables.
The way in which the LUT is initialized may impact the effectiveness of protection against side-channel attacks, and it is difficult to obtain protection from high-order attacks. In general, a side-channel attack is defined as v-variant if it combines a number v of time instances, for example clock cycles, of the controlled physical manifestation, and is said to be of the d-th order if it requires statistical momenta of order d to be considered for distinguishing the correct hypotheses from the erroneous ones.
It is known, for example, to use as a countermeasure against side-channel attacks operations of linear, Boolean, masking of the data. According to this technique, each datum is masked via a Boolean XOR operation with mask values. It is convenient to incorporate also the mask values in the look-up table.
It is known in general to initialize a look-up table where there are input data din, e.g., the data that indicate the address or location of the values to be retrieved in the table, via a first input mask R1 and to mask output data dout, e.g., the values retrieved at the address or location specified by the input data din, via a first output mask R2. This is done by storing in the location of the look-up table corresponding to the address given by din⊕R1, e.g., by the XOR operation between the input data din and the first input mask R1, a value given by dout⊕R2, e.g., by the XOR operation between the output data dout and the first output mask R2. This is usually done one at a time for all the possible values of the input data din and performing the operation of storage in the look-up table of the corresponding output data.
The so-called high order side-channel attacks attack different points of the algorithm that use the same mask values so that the protection of the aforesaid mask can be removed. In general, given a mask, initialization of the look-up table with this mask and access to the masked data during computation means having at least two different operations in two different cycles that use one and the same mask, the corresponding attack thus qualifying as second-order attack.
In the above context, the countermeasures against high-order attacks are usually complex and are very penalizing in terms of latency time and circuit area required for their implementation. Moreover, in hardware implementations, the level of protection may need to be defined at the moment of design, because this affects the design itself and, as has been said, the area of the circuit to be designed. This constitutes a further complexity and drawback.
The foregoing is encountered in particular in AES encryption apparatuses, which, as has been said, implement S-Box devices in order to carry out operations, such as, for example, the SubBytes operation, that comprise at least one look-up table, in particular for carrying out the inversion required by the SubBytes operation.
The look-up table that implements the S-Box has a considerable size, and this determines a high latency, which limits the performance of the countermeasures against side-channel attacks.